@Part[Hash, Root = "CLM.MSS"]
@Comment{Chapter of Common Lisp Manual.  Copyright 1984 Guy L. Steele Jr.⎇

@MyChapter[Hash Tables]
@Index[hash table]
@Label{HASH⎇
A hash table is a @xlisp object that can efficiently map a given
@xlisp object to another @xlisp object.
Each hash table has a set of @i[entries], each of which associates a
particular @i[key] with a particular @i[value].  The basic functions
that deal with hash tables can create entries, delete entries, and find
the value that is associated with a given key.  Finding the value is
very fast, even if there are many entries, because hashing is used; this
@Index2[P {property list⎇, S {compared to hash table⎇]
is an important advantage of hash tables over property lists.

@Index2[P {association list⎇, S {compared to hash table⎇]
A given hash table can only associate one @i[value] with a given
@i[key]; if you try to add a second @i[value], it will replace the
first.  Also, adding a value to a hash table is a destructive operation;
the hash table is modified.  By contrast, association lists can be
augmented non-destructively.

Hash tables come in three kinds, the difference being whether the keys
are compared with @f[eq], @f[eql], or @f[equal].  In other words, there
are hash tables that hash on Lisp @i[objects] (using @f[eq] or @f[eql])
and there are hash tables that hash on @i[tree structure]
(using @f[equal]).

Hash tables are created with the function
@f[make-hash-table], which takes various options, including
which kind of hash table to make (the default being the @f[eql] kind).
To look up a key and find
the associated value, use @f[gethash].
New entries are added
to hash tables using @Macref[setf] with @f[gethash].
To remove an entry, use @f[remhash].  Here is a simple example.
@Lisp
(setq a (make-hash-table))
(setf (gethash 'color a) 'brown)
(setf (gethash 'name a) 'fred)
(gethash 'color a) @EV brown
(gethash 'name a) @EV fred
(gethash 'pointy a) @EV @false
@Endlisp

In this example, the symbols @f[color] and @f[name] are being used as
keys, and the symbols @f[brown] and @f[fred] are being used as the
associated values.  The hash table has two items in it, one of which
associates from @f[color] to @f[brown], and the other of which
associates from @f[name] to @f[fred].

Keys do not have to be symbols; they can be any @xLisp object.  Likewise,
values can be any @xlisp object.

When a hash table is first created, it has a @i[size], which is the
maximum number of entries it can hold.  Usually the actual capacity of
the table is somewhat less, since the hashing is not perfectly
collision-free.  With the maximum possible bad luck, the capacity could
be very much less, but this rarely happens.  If so many entries are
added that the capacity is exceeded, the hash table will automatically
grow, and the entries will be @i[rehashed] (new hash values will be
recomputed, and everything will be rearranged so that the fast hash
lookup still works).  This is transparent to the caller; it all happens
automatically.

@Incompatibility{This hash table facility is compatible with @lmlisp.  It
is similar to the hasharray facility of @Interlisp, and some of the
function names are the same.  However, it is @i[not] compatible with
@Interlisp.  The exact details and the order of arguments are designed to
be consistent with the rest of @Maclisp rather than with
@Interlisp.  For instance, the order of arguments to @f[maphash] is
different, there is no ``system hash table,'' and there is not
the @Interlisp restriction that keys and values may not be @false.⎇

@section{Hash Table Functions⎇

This section documents the functions for hash tables, which
use @i[objects] as keys and associate other objects with them.

@Defun[Fun {make-hash-table⎇, Keys = {[test][size][rehash-size][rehash-threshold]⎇]
This function creates and returns a new hash table.
The @Kwd[test] argument determines how keys are compared;
it must be one of the three values @f[#'eq], @f[#'eql], or @f[#'equal],
or one of the three symbols @f[eq], @f[eql], or @f[equal].
If no test is specified, @f[eql] is assumed.

The @Kwd[size] argument
sets the initial size of the hash table, in entries.
(The actual size may be rounded up from the size
you specify to the next ``good'' size, for example to make it a prime number.)
You won't necessarily be able to store precisely
this many entries into the table
before it overflows and becomes bigger, but this argument does serve
as a hint to the implementation of approximately
how many entries you intend to store.

The @Kwd[rehash-size] argument
specifies how much to increase the size of the hash table when it becomes
full.  This can be an integer greater than zero,
which is the number of entries to add, or
it can be a floating-point number greater than one,
which is the ratio of the new size to the old size.
The default value for this argument is implementation-dependent.

The @Kwd[rehash-threshold] argument
specifies how full the hash table can get before it must grow.
This can be an integer greater than zero and less than the @Kwd[rehash-size]
(in which case it will be scaled whenever the table is grown),
or it can be a floating-point number between zero and one.
The default value for this argument is implementation-dependent.

An example of the use of @f[make-hash-table]:
@lisp
(make-hash-table :rehash-size 1.5
		 :size (* number-of-widgets 43))
@Endlisp
@Enddefun

@Defun[Fun {hash-table-p⎇, Args {@i[object]⎇]
@Index2[P {hash table⎇, S {predicate⎇]
@f[hash-table-p] is true if its argument is a hash table,
and otherwise is false.
@Lisp
(hash-table-p x) @EQ (typep x 'hash-table)
@Endlisp
@Enddefun

@Defun[Fun {gethash⎇, Args {@i[key] @i[hash-table] @optional @i[default]⎇]
@f[gethash] finds the entry in @i[hash-table] whose key is @i[key]
and returns the
associated value.  If there is no such entry, @f[gethash] returns @i[default],
which is @false if not specified.

@f[gethash] actually returns two values, the second being a predicate
value that is true if an entry was found, and false if no entry was found.

@Macref[setf] may be used with @f[gethash] to make new entries in a hash
table.  If an entry with the specified @i[key] already exists, it is
removed before the new entry is added.  The @i[default] argument may be
specified to @f[gethash] in this context; it is ignored by @f[setf], but
may be useful in such macros as @f[incf] that are related to @f[setf]:
@lisp
(incf (gethash a-key table 0))
@endlisp
means the approximately the same as
@lisp
(setf (gethash a-key table 0) (+ (gethash a-key table 0) 1))
@endlisp
which in turn would be treated as simply
@lisp
(setf (gethash a-key table) (+ (gethash a-key table 0) 1))
@endlisp
@Enddefun

@Defun[Fun {remhash⎇, Args {@i[key] @i[hash-table]⎇]
@f[remhash] removes
any entry for @i[key] in @i[hash-table].  This is a predicate
that is true if there was an
entry or false if there was not.
@Enddefun

@Defun[Fun {maphash⎇, Args {@i[function] @i[hash-table]⎇]
For each entry in @i[hash-table], @f[maphash] calls
@i[function] on two arguments:
the key of the entry and the value of the entry.
If entries are added to or deleted from the hash table while a @f[maphash]
is in progress, the results are unpredictable, with one exception:
if the @i[function] calls @f[remhash] to remove the entry currently
being processed by the @i[function], or performs a @Macref[setf] of
@f[gethash] on that entry to change the associated value, then those
operations will have the intended effect.
For example:
@lisp
;; Alter every entry in MY-HASH-TABLE, replacing the value with
;; its square root.  Entries with negative values are removed.
(maphash #'(lambda (key val)
	     (if (minusp val)
		 (remhash key my-hash-table)
		 (setf (gethash key my-hash-table)
		       (sqrt val))))
	 my-hash-table)
@endlisp

@f[maphash] returns @false.
@Enddefun

@Defun[Fun {clrhash⎇, Args {@i[hash-table]⎇]
This removes all the entries from @i[hash-table]
amd returns the hash table itself.
@Enddefun

@Defun[Fun {hash-table-count⎇, Args {@i[hash-table]⎇]
This returns the number of entries in the @i[hash-table].
When a hash table is first created or has been cleared,
the number of entries is zero.
@Enddefun

@section[Primitive Hash Function]

The function @f[sxhash] is a convenient tool for the user who needs
to create more complicated hashed data structures than are provided by
@f[hash-table] objects.

@Defun[Fun {sxhash⎇, Args {@i[object]⎇]
@Index[hash table]
@f[sxhash] computes a hash code for an object and returns the hash code as
a non-negative fixnum.  A property of @f[sxhash]
is that @f[(equal @i[x] @i[y])] implies @f[(= (sxhash @i[x]) (sxhash @i[y]))].

The manner in which the hash code is computed is implementation-dependent,
but is independent of the particular ``incarnation'' or ``core image.''
Hash values produced
by @f[sxhash] may be written out to files, for example, and meaningfully
read in again into an instance of the same implementation.
@Enddefun